1. Field of the Invention
The present invention relates to an arbitration circuit and method for arbitrating between a plurality of requests for access to a shared resource. The shared resource can take a variety of forms, for example a bus, a switching fabric, a buffer, a processing element, a shared memory, etc.
2. Description of the Prior Art
The function of an arbiter is to select between multiple asserted requests seeking access to the shared resource. Often there is a need for a “fair” arbiter, which is arranged to apply an arbitration policy so that over time no one request is favoured over any other request. Accordingly, a fair arbiter will ensure that no one request is starved of service by constantly having a lower priority than other requests. In many cases, weak fairness (which ensures freedom from starvation of service), as compared with strong fairness (where for a particular request the arbiter must grant each other request at most once whilst that particular request remains asserted) is sufficient.
The paper “Arbiters: Design Ideas and Coding Styles” by Matt Weber, Synopsys Users Group (SNUG), Boston, Mass., USA, 2001, describes several well-known arbiter designs. The book “Principles and Practices of Interconnection Networks”, by William Dally and Brian Towles, 2004, describes in Chapter 18 (entitled “Arbitration”) both a round-robin arbiter and a matrix arbiter, and contains a general description of fairness in arbitration. The book “Logical Effort: Designing Fast CMOS Circuits” by Sutherland et al, 1999, discusses circuits for a simple priority arbiter and also discusses how wide logic functions can be implemented as optimal trees of gates, giving an example of the decoder implemented in a tree form.
A common design of arbiter is a round-robin arbiter. A round-robin arbiter can give strong fairness when state update circuitry is provided to ensure that the next state of the arbiter has regard to the currently granted request. If only weak fairness is required, a round robin arbiter can again be used, but without the state update circuitry, and indeed the typical solution used to provide a fast starvation-free arbiter (i.e. an arbiter providing weak fairness) uses a round-robin design. The paper “An In-Depth Look at Prior Art in Fast Round-Robin Arbiter Circuits” by Fatih U{hacek over (g)}urda{hacek over (g)} and Onur Baskirt, Özye{hacek over (g)}in University Technical Report: OZU-EF-2011-0001, August 2011, provides a survey of fast round-robin arbiter implementations. The paper “An Optimal Round-Robin Arbiter Design for NoC” by Jou and Lee, Journal of Information Science and Engineering 26, pages 2047 to 2058, 2010, provides another example of a round-robin arbiter.
Other solutions proposed for fast starvation-free arbiters include matrix-based arbiters with a least-recently-granted (LRG) policy or tree arbiters with a pseudo-LRG policy.
Arbiters are often found on the critical path within data processing systems, and accordingly it would be desirable to provide an improved arbiter design for providing fast starvation-free arbitration, which is both smaller and faster than known implementations.